package main.java.com.amanda.innovate;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.utils.Digraph;
import main.java.com.amanda.utils.DirectedEdge;
import main.java.com.amanda.utils.EdgeWeightedDigraph;

import java.util.Scanner;

/**
 * @author amanda
 * @Description 有向图中基于深度优先搜索的顶点排序
 */
public class DepthFirstOrder {
    private boolean[] marked;
    private Queue<Integer> pre; // 所有顶点的前序排列
    private Queue<Integer> post;// 所有顶点的后序排序
    private Stack<Integer> reversePost;// 所有顶点的逆后序排序
    private int[] preorder;
    private int[] postorder;
    private int postCounter;
    private int preCounter;

    public DepthFirstOrder(Digraph G) {
        preorder = new int[G.V()];
        postorder = new int[G.V()];
        pre = new Queue<>();
        post = new Queue<>();
        reversePost = new Stack<>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v])
                dfs(G, v);
        }
    }

    public DepthFirstOrder(EdgeWeightedDigraph G) {
        preorder = new int[G.V()];
        postorder = new int[G.V()];
        post = new Queue<Integer>();
        pre = new Queue<Integer>();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }

    private void dfs(Digraph G, int v) {
        pre.enqueue(v);
        marked[v] = true;
        preorder[v] = preCounter++;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
        post.enqueue(v);
        reversePost.push(v);
        postorder[v] = postCounter++;
    }
    private void dfs(EdgeWeightedDigraph G, int v) {
        marked[v] = true;
        preorder[v] = preCounter++;
        pre.enqueue(v);
        for (DirectedEdge e : G.adj(v)) {
            int w = e.to();
            if (!marked[w]) {
                dfs(G, w);
            }
        }
        post.enqueue(v);
        postorder[v] = postCounter++;
    }

    public Iterable<Integer> pre() {
        return pre;
    }
    public Iterable<Integer> post() {
        return post;
    }
    public Iterable<Integer> reversePost() {
        return reversePost;
    }
    public int pre(int v) {
        return preorder[v];
    }

    public int post(int v) {
        return postorder[v];
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Digraph G = new Digraph(scanner);

        DepthFirstOrder dfs = new DepthFirstOrder(G);
        StdOut.println("   v  pre post");
        StdOut.println("--------------");
        for (int v = 0; v < G.V(); v++) {
            StdOut.printf("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v));
        }

        StdOut.print("Preorder:  ");
        for (int v : dfs.pre()) {
            StdOut.print(v + " ");
        }
        StdOut.println();

        StdOut.print("Postorder: ");
        for (int v : dfs.post()) {
            StdOut.print(v + " ");
        }
        StdOut.println();

        StdOut.print("Reverse postorder: ");
        for (int v : dfs.reversePost()) {
            StdOut.print(v + " ");
        }
        StdOut.println();
    }
}
/*
13 15
2 3 0 6 0 1 2 0 11 12 9 12 9 10 9 11 3 5 8 7 5 4 0 5 6 4 6 9 7 6
   v  pre post
--------------
   0    0    8
   1    3    2
   2    9   10
   3   10    9
   4    2    0
   5    1    1
   6    4    7
   7   11   11
   8   12   12
   9    5    6
  10    8    5
  11    6    4
  12    7    3
Preorder:  0 5 4 1 6 9 11 12 10 2 3 7 8
Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8
Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4
 */
